package uk.org.landeg.euler.problems;

import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;

public class Problem031 extends AbstractProblem{
	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem031());
		launcher.solve();		
	}

	@Override
	public String getDescription() {
		return "How many different ways can £2 be made using any number of coins?";
	}

	@Override
	public Integer getProblemNumber() {
		return 31;
	}
	
	@Override
	public Object solve() {
		notes.add("This is a partition problem - but we are going to solve by brute force");
		int count = 0;
		for (int n200 = 0 ; n200 < 2 ; n200++) {
			for (int n100 = 0 ; n100 < 3 ; n100++) {
				for (int n50 = 0 ; n50 < 5 ; n50++) {
					for (int n20 = 0 ; n20 < 11 ; n20++) {
						for (int n10 = 0 ; n10 < 21 ; n10++) {
							for (int n5 = 0 ; n5 < 41 ; n5++) {
								for (int n2 = 0 ; n2 < 101 ; n2++) {
									for (int n1 = 0 ; n1 < 201 ; n1++) {
										if (200 * n200 + 
												100 * n100 + 
												20 * n20 + 
												50 * n50 + 
												10 * n10 +
												5 * n5 + 
												2 * n2 + 
												n1 == 200) {
											count++;
										}
									}
								}
							}
						}
					}
				}
			}
		}
		return count;
	}
}
